package com.javabasic.algorithm.sword_of_offer;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see [剑指 Offer II 088. 爬楼梯的最少成本](https://leetcode-cn.com/problems/GzCJIP/)
 * @since Created by work on 2021/12/11 9:29 下午
 */
public class 爬楼梯的最少成本 {

    /**
     * DP解法
     * 当i>=2的时候，就会有dp[i] = min(dp[i-1],dp[i-2])
     * 最后一步，就是max(dp[len-1],dp[len-2])
     * @param cost
     * @return
     */
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < len; i++) {
            dp[i] = Math.min(dp[i-1],dp[i-2]) + cost[i];
        }
        int result = Math.min(dp[len-1],dp[len-2]);
        return result;
    }

    /**
     * DP解法
     * 当i>=2的时候，就会有dp[i] = min(dp[i-1],dp[i-2])
     * 最后一步，就是max(dp[len-1],dp[len-2])
     *
     * dp数组可以直接使用cost替换
     * @param cost
     * @return
     */
    public int minCostClimbingStairs2(int[] cost) {
        int len = cost.length;
        for (int i = 2; i < len; i++) {
            cost[i] = Math.min(cost[i-1],cost[i-2]) + cost[i];
        }
        int result = Math.min(cost[len-1],cost[len-2]);
        return result;
    }
}
